#include <stdio.h>
#include <malloc.h>
#include <mqoai.h>

typedef char VertexType; // 顶点类型用户可自定义
typedef int EdgeType; // 边上的权值类型用户可自定义
#define MAXVEX 9
Boolean visited[MAXVEX];

typedef struct EdgeNode {
    int adjVex;
    EdgeType info;
    struct EdgeNode *next;
}EdgeNode;

typedef struct VertexNode{
    VertexType data;
    struct EdgeNode *firstEdge;
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numNodes, numEdges;
}GraphAdjList;

// 队列的结构（顺序表和链表的实现不一样，可查看之前线性结构部分）
typedef struct Queue{}*Queue;

void initQueue(Queue *Q){}
void EnQueue(Queue *Q, int i){}
void DeQueue(Queue *Q, int i){}
Boolean QueueEmpty(Queue *Q){}

void BFSTraverse(GraphAdjList GL) {
    int i;
    EdgeNode *p;
    Queue Q;
    for(i  = 0; i < GL.numNodes; i++) {
        visited[i] = FALSE;
    }
    // 初始化辅助队列
    initQueue(&Q);
    for(i = 0; i < GL.numNodes; i++) {
        // 访问结点
        visited[i] = TRUE;
        printf("%c", GL.adjList[i].data);
        // 访问过后的就入队
        EnQueue(&Q, i);
        // 当队列非空时，就出队
        while (!QueueEmpty(&Q)) {
            DeQueue(&Q, i);
            // 寻找出队节点的邻接节点
            p = GL.adjList[i].firstEdge;
            // 当邻接点未被访问过就访问后入队
            while (p) {
                if(!visited[p->adjVex]) {
                    visited[p->adjVex] =  TRUE;
                    printf("%c", GL.adjList[p->adjVex].data);
                    EnQueue(&Q, p->adjVex);
                }
                p = p->next;
            }
        }
    }
}